1. Field
The present invention relates generally to data analysis, and more specifically, to expediting queries specifying patterns that unfold over time.
2. Description of the Related Art
Geolocation analytics platforms are generally used to understand human behavior. Such systems map data about places to geographic locations and then this mapping is used to analyze patterns in human behavior based on people's presence in those geographic locations. For example, researchers may use such systems to understand patterns in health, educational, crime, or political outcomes in geographic areas. And some companies use such systems to understand the nature of their physical locations, analyzing, for instance, the demographics of customers who visit their stores, restaurants, or other facilities. Some companies use such systems to measure and understand the results of TV advertising campaigns, detecting changes in the types of customers who visit stores following a campaign. Some companies use geolocation analytics platforms to target content to geolocations, e.g., selecting content like business listings, advertisements, billboards, mailings, restaurant reviews, and the like, based on human behavior associated with locations to which the content is directed. In many contexts, location can be a useful indicator of human behavior.
It is increasingly common for geolocation analytics platforms to contain large data sets, as often arise in the context of analyzing web-scale data sets describing user behavior on a network. In some cases, relatively rich location histories of individual users are obtained based on mobile device usage indicating 1) places the user visits; and 2) attributes of the places the users visit at the time of the visit. In many cases, the number of users for which such data is obtained is relatively large, e.g., well over one million users.
Certain types of queries for users profiles in (or based on) geolocation analytics platforms do not scale well. Typically, user profiles contain records of activities that unfold over time, and some queries specify temporal patterns in those activities. Often queries that are very intuitive for a human to understand can become computationally infeasible when applied to a large data set, e.g., queries for certain patterns in a user's behavior constitute a combinatorial optimization problem that scales poorly as 1) the number of user profiles at issue increase; 2) the number of activities recorded in each profile increase; and 3) the number of criteria in the query increase.